package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}8:58
 */
public class LeetCode222 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public int countNodes(TreeNode root) {
        if (root == null){
            return 0;
        }
        return 1 + countNodes(root.left)+countNodes(root.right);

    }
    //方法二：利用完全二叉树的特性：干满二叉树和完全二叉树，满二叉树直接根据层高h计算出节点为2^h-1，然后继续计算子树中完全二叉树节点。
    //对任意一个子树，遍历其左子树层高left，右子树层高right，相等左子树则是满二叉树，否则右子树是满二叉树
    public int countNodes2(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = countLevel(root.left);
        int right = countLevel(root.right);
        if(left == right){
            return countNodes2(root.right) + (1<<left);
        }else{
            return countNodes2(root.left) + (1<<right);
        }
    }
    private int countLevel(TreeNode root){
        int level = 0;
        while(root != null){
            level++;
            root = root.left;
        }
        return level;
    }

}
